package _go

import "fmt"

/*42. 接雨水
难度
困难

2777

收藏

分享
切换为英文
接收动态
反馈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。



示例 1：



输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9
*/
//暴力破解
//动态规划
//单调栈 单调递减栈
func trapStack(height []int) int {
	l := len(height)
	if l <= 2 {
		return 0
	}
	res := 0
	//单调栈 存储数组下表 入栈的条件为小于栈顶元素的值 即可入栈
	//栈内元素充当做边界
	//循环为有边界 计算每个站内元素元素给有边界的存水量
	stack := []int{}

	for k, v := range height {
		for len(stack) > 0 && v > height[stack[len(stack)-1]] {
			//先弹出栈顶元素
			top := stack[len(stack)-1]
			//出栈
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}

			//再取出刚才栈顶元素的左边一个元素当成左边界
			left := stack[len(stack)-1]
			//开始计算存水量
			//高度  当前遍历值为右边界 两个值取最小值 减去刚才弹出的栈的高度就是这次积水量
			h := min(height[left], v) - height[top]
			//宽度
			w := k - left - 1
			res += w * h
		}
		stack = append(stack, k)
		fmt.Printf("stack1 %+V \n", stack)
	}

	return res
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//双指针解法
func trap(height []int) int {
	l := len(height)
	if l <= 1 {
		return 0
	}
	res := 0
	//双指针发
	left, right := 0, l-1
	leftMax, rightMax := 0, 0
	//不相遇就继续便利
	for left < right {
		//动态维护两个最大值
		leftMax = max(height[left], leftMax)
		rightMax = max(height[right], rightMax)

		//如果 height[left] < height[right] 那势必就有 lMax < rMax
		//因为接到的雨水是由最小值决定的 就是lMax -  height[left] 并且 Left向后移动
		if height[left] < height[right] {
			res += leftMax - height[left]
			left++
		} else {
			res += rightMax - height[right]
			right--
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

//动态规划方式 思想是判断每个位置的最右两边的最大值 就可能算出此位置的积水量
//有两个 优化点 1 每个位置向左遍历一次 查看这个节点向左边的最大值
//				同理 从节点最后向前遍历 查看每个节点向右看的最大值
//				两个数组合并一起就是每个节点左右两边的最大值
//优化点2  最大值记录不需要单独开辟一个单独的空间 只需要用i-1 或者i+1当做最大值即可
func trap(height []int) int {
	if len(height) <= 1 {
		return 0
	}
	n := len(height)
	//记录节点向左看的最大值
	heightL := make([]int, n)
	heightL[0] = height[0]
	for i := 1; i < n; i++ {
		heightL[i] = max(heightL[i-1], height[i])
	}

	//记录节点向右看的最大值
	heightR := make([]int, n)
	heightR[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		heightR[i] = max(heightR[i+1], height[i])
	}
	res := 0
	for k, v := range height {
		res += min(heightL[k], heightR[k]) - v
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
